/**
 * 分发糖果
 *
 * n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
 * 你需要按照以下要求，给这些孩子分发糖果：
 * 每个孩子至少分配到 1 个糖果。
 * 相邻两个孩子中，评分更高的那个会获得更多的糖果。
 * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
 *
 * 示例 1：
 * 输入：ratings = [1,0,2]
 * 输出：5
 * 解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
 *
 * 示例 2：
 * 输入：ratings = [1,2,2]
 * 输出：4
 * 解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
 *      第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
 *
 * 提示：
 * n == ratings.length
 * 1 <= n <= 2 * 104
 * 0 <= ratings[i] <= 2 * 104
 */

import java.util.Arrays;

/**
 * 1. 暴力解法
 * i 位置的最小糖果数取决于两个地方, 一个就是前面一个数, 还有一个就是后面比它小的数
 * 要是前面一个数比它小的话, 它的最小值应该要保证大于前面一个的最小糖果数加一
 * 要是后面有连续比它小的数, 它要保证的是一直连加上来, 最后取的是两个的最大值,
 * 因为这两个都是要保证的
 * 时间复杂度 : O(n ^ 2)
 * 空间复杂度 : O(n)
 *
 *
 * 2. 左右轮流遍历
 * 我们可以通过画图发现, 我们从左向右遍历的时候, 有的数据, 我们总是顾虑不到的
 * 因为后面的数怎样, 我们前面无从得知, 但是后面的数据咋样, 我们从后面遍历的时
 * 候可以知道呀, 所以我们只要遍历两遍, 一个从前向后, 一个从后向前, 然后取同位
 * 置的最大值, 就可以解决这个位置的最小糖果数了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(n)
 */

public class Main {

    // ************************************************
    // 1. 暴力解法
    public int candy1(int[] nums) {

        int n = nums.length;

        // 数组用来记录每个位置的最小糖果数
        int[] dp = new int[n];

        // 这里要初始化第一个位置
        dp[0] = minRating(nums, 0, n);


        // 后面的位置两个方向考虑
        for (int i = 1; i < n; i++) {

            // 第一个方向, 前面一个数
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 0;
            }

            // 考虑后面的数
            int k = minRating(nums, i, n);
            dp[i] = Math.max(k, dp[i]);
        }

        // 求和
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += dp[i];
        }

        // 返回结果
        return sum;
    }

    /**
     * 求后面有几个连着比他小的数
     * @param nums 数组
     * @param i    开始下标
     * @param n    数组长度
     * @return
     */
    private int minRating (int[] nums, int i, int n) {

        // 这里每个最小的是 1, 所以初始化为 1
        int k = 1;

        // 保证系哦啊表不要越界, 我们处理一下标
        i++;

        for (; i < n; i++) {

            if (nums[i] < nums[i - 1]) {

                // 比它小的连着加一
                k++;
            } else {

                // 一比它大就返回
                break;
            }
        }

        // 返回个数
        return k;
    }

    // ****************************************************
    // 2. 左右轮流遍历
    public int candy(int[] nums) {

        int n = nums.length;

        // 两个数组分别用来存储前后遍历的结果
        int[] left = new int[n];
        int[] right = new int[n];

        // 初始话数组
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);

        for(int i = 1; i < n; i++){
            if(nums[i] > nums[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }

        for(int i = n - 2; i >= 0; i--) {
            if(nums[i] > nums[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }

        int count = 0;

        for (int i = 0; i < n; i++) {

            // 计算总和
            count += Math.max(left[i], right[i]);
        }

        // 返回结果
        return count;
    }

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        test.candy(new int[]{1,0,2});
    }
}